1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.collect;
18
19 import static com.google.common.collect.BoundType.CLOSED;
20 import static com.google.common.truth.Truth.assertThat;
21 import static java.util.Collections.sort;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.GwtIncompatible;
25 import com.google.common.collect.testing.Helpers.NullsBeforeB;
26 import com.google.common.collect.testing.NavigableSetTestSuiteBuilder;
27 import com.google.common.collect.testing.TestStringSetGenerator;
28 import com.google.common.collect.testing.features.CollectionFeature;
29 import com.google.common.collect.testing.features.CollectionSize;
30 import com.google.common.collect.testing.google.MultisetFeature;
31 import com.google.common.collect.testing.google.SortedMultisetTestSuiteBuilder;
32 import com.google.common.collect.testing.google.TestStringMultisetGenerator;
33
34 import junit.framework.Test;
35 import junit.framework.TestCase;
36 import junit.framework.TestSuite;
37
38 import java.lang.reflect.Method;
39 import java.util.Arrays;
40 import java.util.Collections;
41 import java.util.Comparator;
42 import java.util.List;
43 import java.util.Set;
44 import java.util.SortedSet;
45
46
47
48
49
50
51 @GwtCompatible(emulated = true)
52 public class TreeMultisetTest extends TestCase {
53
54 @GwtIncompatible("suite")
55 public static Test suite() {
56 TestSuite suite = new TestSuite();
57 suite.addTest(SortedMultisetTestSuiteBuilder
58 .using(new TestStringMultisetGenerator() {
59 @Override
60 protected Multiset<String> create(String[] elements) {
61 return TreeMultiset.create(Arrays.asList(elements));
62 }
63
64 @Override
65 public List<String> order(List<String> insertionOrder) {
66 return Ordering.natural().sortedCopy(insertionOrder);
67 }
68 })
69 .withFeatures(CollectionSize.ANY, CollectionFeature.KNOWN_ORDER,
70 CollectionFeature.GENERAL_PURPOSE,
71 CollectionFeature.SERIALIZABLE,
72 CollectionFeature.ALLOWS_NULL_QUERIES,
73 MultisetFeature.ENTRIES_ARE_VIEWS)
74 .named("TreeMultiset, Ordering.natural")
75 .createTestSuite());
76 suite.addTest(SortedMultisetTestSuiteBuilder
77 .using(new TestStringMultisetGenerator() {
78 @Override
79 protected Multiset<String> create(String[] elements) {
80 Multiset<String> result = TreeMultiset.create(NullsBeforeB.INSTANCE);
81 Collections.addAll(result, elements);
82 return result;
83 }
84
85 @Override
86 public List<String> order(List<String> insertionOrder) {
87 sort(insertionOrder, NullsBeforeB.INSTANCE);
88 return insertionOrder;
89 }
90 })
91 .withFeatures(CollectionSize.ANY, CollectionFeature.KNOWN_ORDER,
92 CollectionFeature.GENERAL_PURPOSE,
93 CollectionFeature.SERIALIZABLE,
94 CollectionFeature.ALLOWS_NULL_VALUES,
95 MultisetFeature.ENTRIES_ARE_VIEWS)
96 .named("TreeMultiset, NullsBeforeB")
97 .createTestSuite());
98 suite.addTest(NavigableSetTestSuiteBuilder.using(new TestStringSetGenerator() {
99 @Override
100 protected Set<String> create(String[] elements) {
101 return TreeMultiset.create(Arrays.asList(elements)).elementSet();
102 }
103
104 @Override
105 public List<String> order(List<String> insertionOrder) {
106 return Lists.newArrayList(Sets.newTreeSet(insertionOrder));
107 }
108 })
109 .named("TreeMultiset[Ordering.natural].elementSet")
110 .withFeatures(
111 CollectionSize.ANY,
112 CollectionFeature.REMOVE_OPERATIONS,
113 CollectionFeature.ALLOWS_NULL_QUERIES)
114 .createTestSuite());
115 suite.addTestSuite(TreeMultisetTest.class);
116 return suite;
117 }
118
119 public void testCreate() {
120 TreeMultiset<String> multiset = TreeMultiset.create();
121 multiset.add("foo", 2);
122 multiset.add("bar");
123 assertEquals(3, multiset.size());
124 assertEquals(2, multiset.count("foo"));
125 assertEquals(Ordering.natural(), multiset.comparator());
126 assertEquals("[bar, foo x 2]", multiset.toString());
127 }
128
129 public void testCreateWithComparator() {
130 Multiset<String> multiset = TreeMultiset.create(Collections.reverseOrder());
131 multiset.add("foo", 2);
132 multiset.add("bar");
133 assertEquals(3, multiset.size());
134 assertEquals(2, multiset.count("foo"));
135 assertEquals("[foo x 2, bar]", multiset.toString());
136 }
137
138 public void testCreateFromIterable() {
139 Multiset<String> multiset
140 = TreeMultiset.create(Arrays.asList("foo", "bar", "foo"));
141 assertEquals(3, multiset.size());
142 assertEquals(2, multiset.count("foo"));
143 assertEquals("[bar, foo x 2]", multiset.toString());
144 }
145
146 public void testToString() {
147 Multiset<String> ms = TreeMultiset.create();
148 ms.add("a", 3);
149 ms.add("c", 1);
150 ms.add("b", 2);
151
152 assertEquals("[a x 3, b x 2, c]", ms.toString());
153 }
154
155 public void testElementSetSortedSetMethods() {
156 TreeMultiset<String> ms = TreeMultiset.create();
157 ms.add("c", 1);
158 ms.add("a", 3);
159 ms.add("b", 2);
160 SortedSet<String> elementSet = ms.elementSet();
161
162 assertEquals("a", elementSet.first());
163 assertEquals("c", elementSet.last());
164 assertEquals(Ordering.natural(), elementSet.comparator());
165
166 assertThat(elementSet.headSet("b")).has().exactly("a").inOrder();
167 assertThat(elementSet.tailSet("b")).has().exactly("b", "c").inOrder();
168 assertThat(elementSet.subSet("a", "c")).has().exactly("a", "b").inOrder();
169 }
170
171 public void testElementSetSubsetRemove() {
172 TreeMultiset<String> ms = TreeMultiset.create();
173 ms.add("a", 1);
174 ms.add("b", 3);
175 ms.add("c", 2);
176 ms.add("d", 1);
177 ms.add("e", 3);
178 ms.add("f", 2);
179
180 SortedSet<String> elementSet = ms.elementSet();
181 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
182 SortedSet<String> subset = elementSet.subSet("b", "f");
183 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
184
185 assertTrue(subset.remove("c"));
186 assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder();
187 assertThat(subset).has().exactly("b", "d", "e").inOrder();
188 assertEquals(10, ms.size());
189
190 assertFalse(subset.remove("a"));
191 assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder();
192 assertThat(subset).has().exactly("b", "d", "e").inOrder();
193 assertEquals(10, ms.size());
194 }
195
196 public void testElementSetSubsetRemoveAll() {
197 TreeMultiset<String> ms = TreeMultiset.create();
198 ms.add("a", 1);
199 ms.add("b", 3);
200 ms.add("c", 2);
201 ms.add("d", 1);
202 ms.add("e", 3);
203 ms.add("f", 2);
204
205 SortedSet<String> elementSet = ms.elementSet();
206 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
207 SortedSet<String> subset = elementSet.subSet("b", "f");
208 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
209
210 assertTrue(subset.removeAll(Arrays.asList("a", "c")));
211 assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder();
212 assertThat(subset).has().exactly("b", "d", "e").inOrder();
213 assertEquals(10, ms.size());
214 }
215
216 public void testElementSetSubsetRetainAll() {
217 TreeMultiset<String> ms = TreeMultiset.create();
218 ms.add("a", 1);
219 ms.add("b", 3);
220 ms.add("c", 2);
221 ms.add("d", 1);
222 ms.add("e", 3);
223 ms.add("f", 2);
224
225 SortedSet<String> elementSet = ms.elementSet();
226 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
227 SortedSet<String> subset = elementSet.subSet("b", "f");
228 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
229
230 assertTrue(subset.retainAll(Arrays.asList("a", "c")));
231 assertThat(elementSet).has().exactly("a", "c", "f").inOrder();
232 assertThat(subset).has().exactly("c").inOrder();
233 assertEquals(5, ms.size());
234 }
235
236 public void testElementSetSubsetClear() {
237 TreeMultiset<String> ms = TreeMultiset.create();
238 ms.add("a", 1);
239 ms.add("b", 3);
240 ms.add("c", 2);
241 ms.add("d", 1);
242 ms.add("e", 3);
243 ms.add("f", 2);
244
245 SortedSet<String> elementSet = ms.elementSet();
246 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
247 SortedSet<String> subset = elementSet.subSet("b", "f");
248 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
249
250 subset.clear();
251 assertThat(elementSet).has().exactly("a", "f").inOrder();
252 assertThat(subset).isEmpty();
253 assertEquals(3, ms.size());
254 }
255
256 public void testCustomComparator() throws Exception {
257 Comparator<String> comparator = new Comparator<String>() {
258 @Override
259 public int compare(String o1, String o2) {
260 return o2.compareTo(o1);
261 }
262 };
263 TreeMultiset<String> ms = TreeMultiset.create(comparator);
264
265 ms.add("b");
266 ms.add("c");
267 ms.add("a");
268 ms.add("b");
269 ms.add("d");
270
271 assertThat(ms).has().exactly("d", "c", "b", "b", "a").inOrder();
272
273 SortedSet<String> elementSet = ms.elementSet();
274 assertEquals("d", elementSet.first());
275 assertEquals("a", elementSet.last());
276 assertEquals(comparator, elementSet.comparator());
277 }
278
279 public void testNullAcceptingComparator() throws Exception {
280 Comparator<String> comparator = Ordering.<String>natural().nullsFirst();
281 TreeMultiset<String> ms = TreeMultiset.create(comparator);
282
283 ms.add("b");
284 ms.add(null);
285 ms.add("a");
286 ms.add("b");
287 ms.add(null, 2);
288
289 assertThat(ms).has().exactly(null, null, null, "a", "b", "b").inOrder();
290 assertEquals(3, ms.count(null));
291
292 SortedSet<String> elementSet = ms.elementSet();
293 assertEquals(null, elementSet.first());
294 assertEquals("b", elementSet.last());
295 assertEquals(comparator, elementSet.comparator());
296 }
297
298 private static final Comparator<String> DEGENERATE_COMPARATOR =
299 new Comparator<String>() {
300 @Override
301 public int compare(String o1, String o2) {
302 return o1.length() - o2.length();
303 }
304 };
305
306
307
308
309
310 public void testDegenerateComparator() throws Exception {
311 TreeMultiset<String> ms = TreeMultiset.create(DEGENERATE_COMPARATOR);
312
313 ms.add("foo");
314 ms.add("a");
315 ms.add("bar");
316 ms.add("b");
317 ms.add("c");
318
319 assertEquals(2, ms.count("bar"));
320 assertEquals(3, ms.count("b"));
321
322 Multiset<String> ms2 = TreeMultiset.create(DEGENERATE_COMPARATOR);
323
324 ms2.add("cat", 2);
325 ms2.add("x", 3);
326
327 assertEquals(ms, ms2);
328 assertEquals(ms2, ms);
329
330 SortedSet<String> elementSet = ms.elementSet();
331 assertEquals("a", elementSet.first());
332 assertEquals("foo", elementSet.last());
333 assertEquals(DEGENERATE_COMPARATOR, elementSet.comparator());
334 }
335
336 public void testSubMultisetSize() {
337 TreeMultiset<String> ms = TreeMultiset.create();
338 ms.add("a", Integer.MAX_VALUE);
339 ms.add("b", Integer.MAX_VALUE);
340 ms.add("c", 3);
341
342 assertEquals(Integer.MAX_VALUE, ms.count("a"));
343 assertEquals(Integer.MAX_VALUE, ms.count("b"));
344 assertEquals(3, ms.count("c"));
345
346 assertEquals(Integer.MAX_VALUE, ms.headMultiset("c", CLOSED).size());
347 assertEquals(Integer.MAX_VALUE, ms.headMultiset("b", CLOSED).size());
348 assertEquals(Integer.MAX_VALUE, ms.headMultiset("a", CLOSED).size());
349
350 assertEquals(3, ms.tailMultiset("c", CLOSED).size());
351 assertEquals(Integer.MAX_VALUE, ms.tailMultiset("b", CLOSED).size());
352 assertEquals(Integer.MAX_VALUE, ms.tailMultiset("a", CLOSED).size());
353 }
354
355 @GwtIncompatible("reflection")
356 public void testElementSetBridgeMethods() {
357 for (Method m : TreeMultiset.class.getMethods()) {
358 if (m.getName().equals("elementSet") && m.getReturnType().equals(SortedSet.class)) {
359 return;
360 }
361 }
362 fail("No bridge method found");
363 }
364 }